A unified mixed-integer programming model for simultaneous fluence weight and aperture optimization in VMAT, tomotherapy, and cyberknife

All rights reserved. In this paper, we propose and study a unified mixed-integer programming model that simultaneously optimizes fluence weights and multi-leaf collimator (MLC) apertures in the treatment planning optimization of VMAT, Tomotherapy, and CyberKnife. The contribution of our model is threefold: (i) Our model optimizes the fluence and MLC apertures simultaneously for a given set of control points. (ii) Our model can incorporate all volume limits or dose upper bounds for organs at risk (OAR) and dose lower bound limits for planning target volumes (PTV) as hard constraints, but it can also relax either of these constraint sets in a Lagrangian fashion and keep the other set as hard constraints. (iii) For faster solutions, we propose several heuristic methods based on the MIP model, as well as a meta-heuristic approach. The meta-heuristic is very efficient in practice, being able to generate dose- and machinery-feasible solutions for problem instances of clinical scale, e.g., obtaining feasible treatment plans to cases with 180 control points, 6750 sample voxels and 18,000 beamlets in 470 seconds, or cases with 72 control points, 8000 sample voxels and 28,800 beamlets in 352 seconds. With discretization and down-sampling of voxels, our method is capable of tackling a treatment field of 8000-64,000cm3, depending on the ratio of critical structure versus unspecified tissues.

On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches

The Kidney Exchange Problem (KEP) is a combinatorial optimization problem and has attracted the attention from the community of integer programming/combinatorial optimisation in the past few years. Defined on a directed graph, the KEP has two variations: one concerns cycles only, and the other, cycles as well as chains on the same graph. We call the former a Cardinality Constrained Multi-cycle Problem (CCMcP) and the latter a Cardinality Constrained Cycles and Chains Problem (CCCCP). The cardinality for cycles is restricted in both CCMcP and CCCCP. As for chains, some studies in the literature considered cardinality restrictions, whereas others did not. The CCMcP can be viewed as an Asymmetric Travelling Salesman Problem that does allow subtours, however these subtours are constrained by cardinality, and that it is not necessary to visit all vertices. In existing literature of the KEP, the cardinality constraint for cycles is usually considered to be small (to the best of our knowledge, no more than six). In a CCCCP, each vertex on the directed graph can be included in at most one cycle or chain, but not both. The CCMcP and the CCCCP are interesting and challenging combinatorial optimization problems in their own rights, particularly due to their similarities to some travelling salesman- and vehicle routing-family of problems. In this paper, our main focus is to review the existing mathematical programming models and solution methods in the literature, analyse the performance of these models, and identify future research directions. Further, we propose a polynomial-sized and an exponential-sized mixed-integer linear programming model, discuss a number of stronger constraints for cardinality-infeasible-cycle elimination for the latter, and present some preliminary numerical results.

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.

Joint resource allocation for max-min throughput in multicell networks

We investigate the resource-allocation problem in multicell networks targeting the max-min throughput of all cells. A joint optimization over power control, channel allocation, and user association is considered, and the problem is then formulated as a nonconvex mixed-integer nonlinear problem (MINLP). To solve this problem, we proposed an alternating-optimization-based algorithm, which applies branch-and-bound and simulated annealing in solving subproblems at each optimization step. We also demonstrate the convergence and efficiency of the proposed algorithms by thorough numerical experiments. The experimental results show that joint optimization over all resources outperforms the restricted optimization over individual resources significantly.

A general communication cost optimization framework for big data stream processing in geo-distributed data centers

With the explosion of big data, processing large numbers of continuous data streams, i.e., big data stream processing (BDSP), has become a crucial requirement for many scientific and industrial applications in recent years. By offering a pool of computation, communication and storage resources, public clouds, like Amazon's EC2, are undoubtedly the most efficient platforms to meet the ever-growing needs of BDSP. Public cloud service providers usually operate a number of geo-distributed datacenters across the globe. Different datacenter pairs are with different inter-datacenter network costs charged by Internet Service Providers (ISPs). While, inter-datacenter traffic in BDSP constitutes a large portion of a cloud provider's traffic demand over the Internet and incurs substantial communication cost, which may even become the dominant operational expenditure factor. As the datacenter resources are provided in a virtualized way, the virtual machines (VMs) for stream processing tasks can be freely deployed onto any datacenters, provided that the Service Level Agreement (SLA, e.g., quality-of-information) is obeyed. This raises the opportunity, but also a challenge, to explore the inter-datacenter network cost diversities to optimize both VM placement and load balancing towards network cost minimization with guaranteed SLA. In this paper, we first propose a general modeling framework that describes all representative inter-task relationship semantics in BDSP. Based on our novel framework, we then formulate the communication cost minimization problem for BDSP into a mixed-integer linear programming (MILP) problem and prove it to be NP-hard. We then propose a computation-efficient solution based on MILP. The high efficiency of our proposal is validated by extensive simulation based studies.

Energy minimization in multi-task software-defined sensor networks

Abstract—
After a decade of extensive research on application-specific wireless sensor networks (WSNs), the recent development of information and communication technologies makes it practical to realize the software-defined sensor networks (SDSNs), which are able to adapt to various application requirements and to fully explore the resources of WSNs. A sensor node in SDSN is able to conduct multiple tasks with different sensing targets simultaneously. A given sensing task usually involves multiple sensors to achieve a certain quality-of-sensing, e.g., coverage ratio. It is significant to design an energy-efficient sensor scheduling and management strategy with guaranteed quality-of-sensing for all tasks. To this end, three issues are investigated in this paper: 1) the subset of sensor nodes that shall be activated, i.e., sensor activation, 2) the task that each sensor node shall be assigned, i.e., task mapping, and 3) the sampling rate on a sensor for a target, i.e., sensing scheduling. They are jointly considered and formulated as a mixed-integer with quadratic constraints programming (MIQP) problem, which is then reformulated into a mixed-integer linear programming (MILP) formulation with low computation complexity via linearization. To deal with dynamic events such as sensor node participation and departure, during SDSN operations, an efficient online algorithm using local optimization is developed. Simulation results show that our proposed online algorithm approaches the globally optimized network energy efficiency with much lower rescheduling time and control overhead.

Stochastic optimization models for energy management in carbonization process of carbon fiber production

Industrial producers face the task of optimizing production process in an attempt to achieve the desired quality such as mechanical properties with the lowest energy consumption. In industrial carbon fiber production, the fibers are processed in bundles containing (batches) several thousand filaments and consequently the energy optimization will be a stochastic process as it involves uncertainty, imprecision or randomness. This paper presents a stochastic optimization model to reduce energy consumption a given range of desired mechanical properties. Several processing condition sets are developed and for each set of conditions, 50 samples of fiber are analyzed for their tensile strength and modulus. The energy consumption during production of the samples is carefully monitored on the processing equipment. Then, five standard distribution functions are examined to determine those which can best describe the distribution of mechanical properties of filaments. To verify the distribution goodness of fit and correlation statistics, the Kolmogorov-Smirnov test is used. In order to estimate the selected distribution (Weibull) parameters, the maximum likelihood, least square and genetic algorithm methods are compared. An array of factors including the sample size, the confidence level, and relative error of estimated parameters are used for evaluating the tensile strength and modulus properties. The energy consumption and N2 gas cost are modeled by Convex Hull method. Finally, in order to optimize the carbon fiber production quality and its energy consumption and total cost, mixed integer linear programming is utilized. The results show that using the stochastic optimization models, we are able to predict the production quality in a given range and minimize the energy consumption of its industrial process.

Combining extension matrix and integer programming for optimal concept learning

This paper proposes two integer programming models and their GA-based solutions for optimal concept learning. The models are built to obtain the optimal concept description in the form of propositional logic formulas from examples based on completeness, consistency and simplicity. The simplicity of the propositional rules is selected as the objective function of the integer programming models, and the completeness and consistency of the concept are used as the constraints. Considering the real-world problems that certain level of noise is contained in data set, the constraints in model 11 are slacked by adding slack-variables. To solve the integer programming models, genetic algorithm is employed to search the global solution space. We call our approach IP-AE. Its effectiveness is verified by comparing the experimental results with other well- known concept learning algorithms: AQ15 and C4.5.

Knowledge extraction from a mixed transfer function artificial neural network

One of the main problems with Artificial Neural Networks (ANNs) is that their results are not intuitively clear. For example, commonly used hidden neurons with sigmoid activation function can approximate any continuous function, including linear functions, but the coefficients (weights) of this approximation are rather meaningless. To address this problem, current paper presents a novel kind of a neural network that uses transfer functions of various complexities in contrast to mono-transfer functions used in sigmoid and hyperbolic tangent networks. The presence of transfer functions of various complexities in a Mixed Transfer Functions Artificial Neural Network (MTFANN) allow easy conversion of the full model into user-friendly equation format (similar to that of linear regression) without any pruning or simplification of the model. At the same time, MTFANN maintains similar generalization ability to mono-transfer function networks in a global optimization context. The performance and knowledge extraction of MTFANN were evaluated on a realistic simulation of the Puma 560 robot arm and compared to sigmoid, hyperbolic tangent, linear and sinusoidal networks.

Benchmark generation algorithm for stochastic mixed model assembly shop simulation and optimization

The Operations Research (OR) community have defined many deterministic manufacturing control problems mainly focused on scheduling. Well-defined benchmark problems provide a mechanism for communication of the effectiveness of different optimization algorithms. Manufacturing problems within industry are stochastic and complex. Common features of these problems include: variable demand, machine part specific breakdown patterns, part machine specific process durations, continuous production, Finished Goods Inventory (FGI) buffers, bottleneck machines and limited production capacity. Discrete Event Simulation (DES) is a commonly used tool for studying manufacturing systems of realistic complexity. There are few reports of detail-rich benchmark problems for use within the simulation optimization community that are as complex as those faced by production managers. This work details an algorithm that can be used to create single and multistage production control problems. The reported software implementation of the algorithm generates text files in eXtensible Markup Language (XML) format that are easily edited and understood as well as being cross-platform compatible. The distribution and acceptance of benchmark problems generated with the algorithm would enable researchers working on simulation and optimization of manufacturing problems to effectively communicate results to benefit the field in general.

The discovery of generalized causal models with mixed variables using MML criterion

One major difficulty frustrating the application of linear causal models is that they are not easily adapted to cope with discrete data. This is unfortunate since most real problems involve both continuous and discrete variables. In this paper, we consider a class of graphical models which allow both continuous and discrete variables, and propose the parameter estimation method and a structure discovery algorithm based on Minimum Message Length and parameter estimation. Experimental results are given to demonstrate the potential for the application of this method.

The domain layer for mixed-initiative interaction in generative design

The design space exploration formalism has developed data structures and algorithms of sufficient complexity and scope to support conceptual layout, massing, and enclosure configurations. However, design remains a human enterprise. To support the user in designing with the formalism, we have developed an interaction model that addresses the interleaving of user actions with the formal operations of design space exploration. The central feature of our interaction model is the modeling of control based on mixed-initiative. Initiative is sometimes taken by the designer and sometimes by the formalism in working on a shared design task. The model comprises three layers, domain, task, and dialogue. In this paper we describe the formulation of the domain layer of our mixed-initiative interaction model for design space exploration. We present the view of the domain as understood in the formalism in terms of the three abstract concepts of state, move, and structure. In order to support mixed initiative, it is necessary to develop a shared view of the domain. The domain layer addresses this problem by mapping the designer's view onto the symbol substrate. First, we present the designer's view of the domain in terms of problems, solutions, choices, and history. Second, we show how this view is interleaved with the symbol-substrate through four domain layer constructs, problem state, solution state, choice, and exploration history. The domain layer presents a suitable foundation for integrating the role of the designer with a description formalism. It enables the designer to maintain exploration freedom in terms of formulating and reformulating problems, generating solutions, making choices, and navigating the history of exploration.

Knowledge extraction from a mixed transfer function artificial neural network

One of the big problems with Artificial Neural Networks (ANN) is that their results are not intuitively clear. For example, if we use the traditional neurons, with a sigmoid activation function, we can approximate any function, including linear functions, but the coefficients (weights) in this approximation will be rather meaningless. To resolve this problem, this paper presents a novel kind of ANN with different transfer functions mixed together. The aim of such a network is to i) obtain a better generalization than current networks ii) to obtain knowledge from the networks without a sophisticated knowledge extraction algorithm iii) to increase the understanding and acceptance of ANNs. Transfer Complexity Ratio is defined to make a sense of the weights associated with the network. The paper begins with a review of the knowledge extraction from ANNs and then presents a Mixed Transfer Function Artificial Neural Network (MTFANN). A MTFANN contains different transfer functions mixed together rather than mono-transfer functions. This mixed presence has helped to obtain high level knowledge and similar generalization comparatively to monotransfer function nets in a global optimization context.

Polyhedral studies for minimum-span graph labelling with integer distance constraints

This paper studies the polytope of the minimum-span graph labelling problems with integer distance constraints (DC-MSGL). We first introduce a few classes of new valid inequalities for the DC-MSGL defined on general graphs and briefly discuss the separation problems of some of these inequalities. These are the initial steps of a branch-and-cut algorithm for solving the DC-MSGL. Following that, we present our polyhedral results on the dimension of the DC-MSGL polytope, and that some of the inequalities are facet defining, under reasonable conditions, for the polytope of the DC-MSGL on triangular graphs.

Application of real and functional analysis to solve boundary value problems

This thesis is about using appropriate tools in functional analysis arid classical analysis to tackle the problem of existence and uniqueness of nonlinear partial differential equations. There being no unified strategy to deal with these equations, one approaches each equation with an appropriate method, depending on the characteristics of the equation. The correct setting of the problem in appropriate function spaces is the first important part on the road to the solution. Here, we choose the setting of Sobolev spaces. The second essential part is to choose the correct tool for each equation. In the first part of this thesis (Chapters 3 and 4) we consider a variety of nonlinear hyperbolic partial differential equations with mixed boundary and initial conditions. The methods of compactness and monotonicity are used to prove existence and uniqueness of the solution (Chapter 3). Finding a priori estimates is the main task in this analysis. For some types of nonlinearity, these estimates cannot be easily obtained, arid so these two methods cannot be applied directly. In this case, we first linearise the equation, using linear recurrence (Chapter 4). In the second part of the thesis (Chapter 5), by using an appropriate tool in functional analysis (the Sobolev Imbedding Theorem), we are able to improve previous results on a posteriori error estimates for the finite element method of lines applied to nonlinear parabolic equations. These estimates are crucial in the design of adaptive algorithms for the method, and previous analysis relies on, what we show to be, unnecessary assumptions which limit the application of the algorithms. Our analysis does not require these assumptions. In the last part of the thesis (Chapter 6), staying with the theme of choosing the most suitable tools, we show that using classical analysis in a proper way is in some cases sufficient to obtain considerable results. We study in this chapter nonexistence of positive solutions to Laplace's equation with nonlinear Neumann boundary condition. This problem arises when one wants to study the blow-up at finite time of the solution of the corresponding parabolic problem, which models the heating of a substance by radiation. We generalise known results which were obtained by using more abstract methods.